package dataStructs.search;

/**
 * @author Jonny Long
 * @date 2021/3/11 19:34
 */
public class MySearch {
    // 线性查找
    public static int seqSearch(double[] arr, int value) {
        // 线性查找是逐一比对，发现有相同值，就返回下标
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == value) {
                return i;
            }
        }
        return -1;
    }

    // 二分查找(非递归)
    public static int binarySearch(double[] arr, int left, int right, double val) {
        while (left <= right) {
            int mid = left + ((right - left) / 2);
            if (arr[mid] == val) {
                return mid;
            } else if (arr[mid] < val) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    // 二分查找(递归)
    public static int binarySearchRecursive(double[] arr, int left, int right, double val) {
        if (left > right) {
            return -1;
        }
        int mid = left + ((right - left) / 2);
        if (arr[mid] == val) {
            return mid;
        } else if (arr[mid] < val) {
            return binarySearchRecursive(arr, mid + 1, right, val);
        } else {
            return binarySearchRecursive(arr, left, mid - 1, val);
        }
    }

    // 插值查找
    public static int insertSearch(double[] arr, int left, int right, double val) {
        if (left > right || val < arr[0] || val > arr[arr.length - 1]) {
            return -1;
        }
        int mid = (int) (left + (right - left) * (val - arr[left]) / (arr[right] - arr[left]));
        if (arr[mid] == val) {
            return mid;
        } else if (arr[mid] < val) {
            return binarySearchRecursive(arr, mid + 1, right, val);
        } else {
            return binarySearchRecursive(arr, left, mid - 1, val);
        }
    }
}
